// poj1155
// 题意：给定一个n(<=3000)的树，每个叶子结点有个权值，每条边有条费用。
//       如果要选某个叶子节点，那么你可以获得它的权值，但是要扣去从
//       根节点到这个叶子节点所有边的费用。（每条边的费用只会被算一次）
//       问，最后整个获得价值非负的情况下，最多可以选到几个叶子结点。
//
// 题解：首先可以得到状态f[i][j]表示第i个节点选择子树里的j个叶子结点最大
//       的价值，最后就是检查最大的f[1][j]大于等于0的j。
//       但是这样转移是O(n^2)的，转移的时候类似一个背包。（转移的时候反着
//       转移）其实我们发现转移的时候无用状态很多，枚举当前往下走的儿子
//       节点选中的叶子结点数肯定不会超过这个儿子对应子树的叶子节点数，
//       枚举当前节点的j的时候肯定不会超过已经做到的这些儿子节点的叶子
//       节点数和，所以我们再维护一个leaf_num来统计每个节点对应子树的叶子
//       节点个数，有了这个优化就可以很快转移。
//
// run: $exec < input
#include <iostream>

int const maxn = 3007;
int const inf = 1 << 29;
int head[maxn], end_point[2 * maxn], cost[2 * maxn], next[2 * maxn];
int alloc = 2;
int f[maxn][maxn];
int value[maxn];
int leaf_num[maxn];
int n, m;

void add_edge(int u, int v, int c)
{
	end_point[alloc] = v; cost[alloc] = c;
	next[alloc] = head[u]; head[u] = alloc++;

	end_point[alloc] = u; cost[alloc] = c;
	next[alloc] = head[v]; head[v] = alloc++;
}

void dp(int u, int parent)
{
	f[u][0] = 0;
	for (int i = 1; i <= m; i++) f[u][i] = -inf;
	if (u >= n - m + 1) { f[u][1] = value[u]; return; }

	for (int p = head[u]; p; p = next[p]) {
		int v = end_point[p], c = cost[p];
		if (v == parent) continue;
		dp(v, u);
		leaf_num[u] += leaf_num[v];
		for (int i = leaf_num[u]; i >= 1; i--) {
			for (int j = 1; j <= leaf_num[v] && j <= i; j++) {
				f[u][i] = std::max(f[u][i], f[u][i - j] + f[v][j] - c);
			}
		}
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin >> n >> m;
	for (int i = 1, k, x, y; i <= n - m; i++) {
		std::cin >> k;
		for (int j = 0; j < k; j++) {
			std::cin >> x >> y;
			add_edge(i, x, y);
		}
	}
	for (int i = n - m + 1; i <= n; i++) {
		leaf_num[i] = 1;
		std::cin >> value[i];
	}
	dp(1, -1);
	int i = m;
	for (; i >= 0; i--) {
//		std::cout << "f[1][" << i << "] = " << f[1][i] << '\n';
		if (f[1][i] >= 0) break;
	}
	std::cout << i << '\n';
}

